Educational Codeforces Round 55 (Rated for Div. 2)

Diposting di | Edited on

传送门

A. Vasya and Book (傻逼题)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    int t;
    cin>>t;
    while(t--){
        ll n,x,y,d;
        cin>>n>>x>>y>>d;

        ll one,two,three;
        one=two=three=inf;
        if((n-y)%d==0){
            one=(n-x)/d;
            if((n-x)%d)one++;
            one+=(n-y)/d;
        }
        else one=inf;
        if((y-1)%d==0){
            two=(x-1)/d;
            if((x-1)%d)two++;
            two+=(y-1)/d;
        }
        else two=inf;
        if(abs(y-x)%d==0){
            three=abs(y-x)/d;
        }
        else three=inf;
        ll ans=min(one,min(two,three));
        if(ans==inf)cout<<-1<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

B.Vova and Trophies （前后缀处理一下)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
char s[maxn];
int pre[maxn];
int erp[maxn];
bool okpre[maxn];
bool okrep[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    cin>>s+1;
    int on=0;

    for(int i=1;i<=n;i++){
        if(s[i]=='G')pre[i]=pre[i-1]+1;
        else pre[i]=0;
        if(s[i]=='G')on++;
    }
    for(int i=n;i>=1;i--){
        if(s[i]=='G')erp[i]=erp[i+1]+1;
        else erp[i]=0;
    }
    /*for(int i=1;i<=n;i++){
        cout<<pre[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<erp[i]<<" ";
    }
    cout<<endl;*/
    int mi=0;
    for(int i=1;i<=n;i++){
        int k=pre[i-1]+erp[i+1];
        if(k!=on)k++;
        mi=max(mi,k);
       // cout<<"i=="<<i<<" "<<mi<<endl;
    }
    cout<<mi<<endl;
    return 0;
}

C.Multi-Subject Competition (算每个数量的贡献)

题意

题意是给出n个人的专长(m种)si和对应的熟练度ri，挑出一部分人组成一个团体，要求团体中每个不同的专长对应的人数一致。求使得团队熟练度总和最大是多少

题解

一开始写了个假算法n方的复杂度 水过去了，结果比赛一结束自己就感觉自己算法会被卡，一觉醒来发现真被hack了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int s[maxn];
int r[maxn];
vector<int>ve[maxn];
int cmp(int a,int b){
    return a>b;
}
vector<ll>num[maxn];
ll ans[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        ve[a].push_back(b);
    }
    int k=0;
    for(int i=1;i<=m;i++){
        sort(ve[i].begin(),ve[i].end(),cmp);
    }
    ll ma=0;
    for(int i=1;i<=m;i++){
        int k=0;
        for(int j=0;j<ve[i].size();j++){
            k+=ve[i][j];
            if(k<=0)break;
            ans[j+1]+=k;
            ma=max(ma,ans[j+1]);
        }
    }
    cout<<ma<<endl;
    return 0;
}

D.Maximum Diameter Graph (满足出度限制的直径最大)

题意

给出n个点以及他们的度数，询问是否可以构造出一幅无自环无重边的无向图且使得图的直径尽可能的大。

题解

答案肯定是一个树，所以构建一个树，然后把度为1的点插到边上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
struct node{
    int id,in;
    bool operator < (const node &a)const{
        return this->in>a.in;
    }
}my[550];
vector<int>ve[550];
void add(int a,int b){
    ve[a].push_back(b);
    ve[b].push_back(a);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,i,j,m=0;
    cin>>n;
    for(i=0;i<n;i++)my[i].id=i,cin>>my[i].in;
    sort(my,my+n);
    int len=0;
    for(i=1;i<n;i++){
        my[i].in--;my[i-1].in--;
        add(my[i].id,my[i-1].id);
        m++;len++;
        if(my[i].in==0)break;
    }
    int mid=i++;
    int ele=0;
    while(i<n){
        bool flag=false;
        for(j=0;j<mid;j++){
            if(my[j].in>0){
                ele=1;flag=1;my[j].in--;my[i].in--;
                add(my[j].id,my[i].id);
                i++;m++;
                break;
            }
        }
        if(!flag)break;
    }
    len+=ele;
    if(i<n){puts("NO");}
    else{
        cout<<"YES "<<len<<endl;
        cout<<m<<endl;
        for(i=0;i<n;i++){
            for(auto k:ve[i]){
                if(k>i)cout<<i+1<<" "<<k+1<<endl;
            }
        }
    }
    return 0;
}

E.Increasing Frequency (贪心求区间最大差值)

题意

给一个长度为n的序列，并且确定一个数c。你可以任选一个区间[l,r],对该区间+k,k可以为负数你可以任选一个区间[l,r],对该区间+k,k可以为负数，使得最后的n个数中，等于c的数字的个数最多。问最多有多少个这样的数？

题解

题目让我们把一个区间的值变换;那最优的方法就是选一个区间 把区间不是c的值变成c同时c又会变成其他值；

所以就是找一个区间里面不是C的值减去C的值+区间外面C的值最大；

那就是怎么找这个区间了，我们可以把前面如果小于C个数的值的个数变成C的个数，然后再加上当前个数。这样就相当于修改了一个值，接下来的区间如果大于C的个数，那就相当于修改了两个；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n,c;
cin>>n>>c;
int ans=0;
while(n--){
    int now;
    cin>>now;
    if(now==c)num[c]++;
    else{
        if(num[now]<=num[c])num[now]=num[c];
        num[now]++;
        ans=max(ans,num[now]-num[c]);
    }
}
cout<<ans+num[c]<<endl;

F.Speed Dial

题意

题解

G.Petya and Graph ( 最大权闭合子图)

题意

让你选一些边，选边的前提是端点都被选了，求最大的边权和-点权和。

题解

模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e4+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
struct Edge{
    int to,next;
    ll v;
}e[maxn];
int head[maxn],cnt=1,n,m,u,v,S,T,d[maxn],t,w,q[maxn],x;ll ans;
void ins(int u,int v,ll w){e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;}
void insert(int u,int v,ll w){ins(u,v,w);ins(v,u,0);}
bool bfs(){
    memset(d,-1,sizeof(d));t=0;w=1;q[0]=S;d[S]=0;
    while(t!=w){
        x=q[t++];for(int i=head[x];i;i=e[i].next)if(e[i].v&&d[e[i].to]==-1)d[e[i].to]=d[x]+1,q[w++]=e[i].to;
    }return d[T]!=-1;
}
ll dfs(int x,ll f){
    if(x==T)return f;ll w,used=0;
    for(int i=head[x];i;i=e[i].next)if(e[i].v&&d[e[i].to]==d[x]+1){
        w=dfs(e[i].to,min(f-used,e[i].v));
        used+=w;e[i].v-=w;e[i^1].v+=w;if(used==f)return f;
    }if(!used)d[x]=-1;return used;
}
ll dinic(ll ans=0){while(bfs())ans+=dfs(S,inf);return ans;}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;T=n+m+1;
    for(int i=1;i<=n;i++)cin>>u,insert(m+i,T,u);
    for(int i=1;i<=m;i++)cin>>u>>v>>w,ans+=w,insert(S,i,w),insert(i,u+m,inf),insert(i,v+m,inf);
    cout<<ans-dinic()<<endl;
    return 0;
}